|
In graph theory, an isomorphism of graphs ''G'' and ''H'' is a bijection between the vertex sets of ''G'' and ''H'' : such that any two vertices ''u'' and ''v'' of ''G'' are adjacent in ''G'' if and only if ƒ(''u'') and ƒ(''v'') are adjacent in ''H''. This kind of bijection is generally called "edge-preserving bijection", in accordance with the general notion of isomorphism being a structure-preserving bijection. If an isomorphism exists between two graphs, then the graphs are called isomorphic and we write . In the case when the bijection is a mapping of a graph onto itself, i.e., when ''G'' and ''H'' are one and the same graph, the bijection is called an automorphism of ''G''. A graph isomorphism is an equivalence relation on graphs and as such it partitions the class of all graphs into equivalence classes. A set of graphs isomorphic to each other is called an isomorphism class of graphs. The two graphs shown below are isomorphic, despite their different looking drawings. ==Variations== In the above definition, graphs are understood to be undirected non-labeled non-weighted graphs. However, the notion of isomorphism may be applied to all other variants of the notion of graph, by adding the requirements to preserve the corresponding additional elements of structure: arc directions, edge weights, etc., with the following exception. When spoken about graph labeling with ''unique labels'', commonly taken from the integer range 1,...,''n'', where ''n'' is the number of the vertices of the graph, two labeled graphs are said to be isomorphic if the corresponding underlying unlabeled graphs are isomorphic. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「graph isomorphism」の詳細全文を読む スポンサード リンク
|